using System;
using System.Collections.Generic;
using System.Text;
using TTDotNet.Util;
using TTDotNet.Engine.Terrain;
using Microsoft.DirectX;

namespace TTDotNet.Engine.Networks
{
    public class DDDRoadNetwork
    {
        private Dictionary<DDDCoordinate, RoadNode> nodes;
        private Dictionary<RoadNode, List<RoadPath>> paths;

        private float[] xChange = { 0f, 0.5f, 0f, -0.5f };
        private float[] zChange = { 0.5f, 0f, -0.5f, 0f };

        public DDDRoadNetwork()
        {
            nodes = new Dictionary<DDDCoordinate, RoadNode>();
            paths = new Dictionary<RoadNode, List<RoadPath>>();
        }

        public bool AddRoad(RoadStrip strip)
        {
            RotateType rotType = strip.start;

            foreach (DDDCoordinate coord in strip.coords)
            {
                AddToNode(coord, rotType, RoadPathType.Road);
                rotType = (RotateType)(((int)rotType + 2) % 4);
            }

            //HEAD ON ROADS - ONE PATH;
            // TUNNEL HEIGHTS STILL BROKE?
            // Landscape highlighting
            // Presentation...

            return true;
        }

        public bool AddTunnel(DDDCoordinate start, DDDCoordinate end)
        {
            RotateType rotType = RotateType.Zero;

            if (start.X < end.X) { rotType = RotateType.Ninety; }
            else if (start.X > end.X) { rotType = RotateType.TwoSeventy; }

            if (start.Z < end.Z) { rotType = RotateType.Zero; }
            else if (start.Z > end.Z) { rotType = RotateType.OneEighty; }

            RotateType oppRot = (RotateType)(((int)rotType + 2) % 4);

            if (!nodes.ContainsKey(start) && !nodes.ContainsKey(end))
            {
                CreateNewNode(start, rotType, RoadPathType.Tunnel);
                AddToNode(start, oppRot, RoadPathType.Tunnel);

                CreateNewNode(end, rotType, RoadPathType.Tunnel);
                AddToNode(end, oppRot, RoadPathType.Tunnel);

                BuildPath(start, end, RoadPathType.Tunnel);
            }
            
            return true;
        }

        private bool AddToNode(DDDCoordinate coord, RotateType rotType, RoadPathType type)
        {
            if (nodes.ContainsKey(coord))
            {
                AddToExisting(coord, rotType, type);
            }
            else
            {
                CreateNewNode(coord, rotType, type);
            }
            return false;
        }

        private bool CreateNewNode(DDDCoordinate coord, RotateType rotType, RoadPathType type)
        {
            List<RoadPath> containing = GetPathsContaining(coord);
            List<RotateType> extra = new List<RotateType>();

            RoadNode node = new RoadNode(coord, rotType, type);
            nodes[coord] = node;

            if (containing.Count > 0)
            {
                if (containing[0].Source.Coordinate.X != containing[0].Destination.Coordinate.X)
                {
                    extra.Add(RotateType.Ninety);
                    extra.Add(RotateType.TwoSeventy);
                }
                else
                {
                    extra.Add(RotateType.Zero);
                    extra.Add(RotateType.OneEighty);
                }
            }

            foreach (RotateType rot in extra)
            {
                node.AddToNode(rot);
            }

            if (containing.Count > 0)
            {
                DDDCoordinate start = containing[0].Source.Coordinate;
                DDDCoordinate end = containing[0].Destination.Coordinate;

                RemovePathsContaining(coord);

                BuildPath(start, coord, type);
                BuildPath(coord, end, type);
            }

            DDDCoordinate neighbour = GetAdjacentTile(coord, rotType);

            if (neighbour != null && nodes.ContainsKey(neighbour))
            {
                ConnectNode(coord, rotType, neighbour, type);
            }

            return true;
        }

        private bool AddToExisting(DDDCoordinate coord, RotateType rotType, RoadPathType type)
        {
            DDDCoordinate neighbour = GetAdjacentTile(coord, rotType);

            TileType before = nodes[coord].RoadType;

            if (nodes[coord].RotateTypes.Contains(rotType))
            {
                return false;
            }
            else
            {
                nodes[coord].AddToNode(rotType);
            }

            if (before == TileType.RoadStraight && nodes[coord].RoadType == TileType.RoadJunction)
            {
                List<RoadPath> containedIn = GetPathsContaining(coord);

                if (containedIn.Count > 0 && (!coord.Equals(containedIn[0].Source.Coordinate) && !coord.Equals(containedIn[0].Destination.Coordinate)))
                {

                    DDDCoordinate start = containedIn[0].Source.Coordinate;
                    DDDCoordinate end = containedIn[0].Destination.Coordinate;

                    RemovePathsContaining(coord);

                    BuildPath(start, coord, type);
                    BuildPath(coord, end, type);
                }
            }

            if (nodes[coord].RoadType != TileType.RoadStraight)
            {
                if (neighbour != null && nodes.ContainsKey(neighbour))
                {
                    ConnectNode(coord, rotType, neighbour, type);
                }
            }
            else
            {
                List<RoadPath> containedIn = GetPathsContaining(coord);

                if (containedIn.Count > 0 && neighbour != null)
                {
                    DDDCoordinate start = containedIn[0].Source.Coordinate;
                    if (start.Equals(coord)) start = containedIn[0].Destination.Coordinate;

                    DDDCoordinate end = neighbour;

                    RemovePathsContaining(coord);

                    BuildPath(start, end, type);

                }
            }

            return false;
        }

        private void ConnectNode(DDDCoordinate coord, RotateType rotType, DDDCoordinate neighbour, RoadPathType type)
        {
            if (nodes[neighbour].RoadType == TileType.RoadStraight)
            {
                List<RoadPath> rps = GetPathsTo(neighbour);

                if (rps.Count == 0)
                {
                    if (CanConnect(coord, neighbour))
                    {
                        BuildPath(coord, neighbour, type);
                    }
                }
                else if (rps.Count == 1)
                {
                    if (CanConnect(coord, neighbour))
                    {
                        if (rps[0].RoadPathType == RoadPathType.Road)
                        {
                            RemovePathsToFrom(neighbour);
                            BuildPath(coord, rps[0].Source.Coordinate, type);
                        }
                        else
                        {
                            BuildPath(coord, neighbour, type);
                        }
                    }
                }
            }
            else
            {
                if (CanConnect(coord, neighbour))
                {
                    BuildPath(coord, neighbour, type);
                }
            }
            
        }

        private void RemovePathsToFrom(DDDCoordinate coord)
        {
            List<RoadPath> list = paths[nodes[coord]];

            foreach (RoadPath rp in list)
            {
                List<RoadPath> opps = paths[nodes[rp.Destination.Coordinate]];

                foreach (RoadPath rp2 in opps)
                {
                    if (rp2.Destination.Coordinate.Equals(coord))
                    {
                        paths[nodes[rp2.Source.Coordinate]].Remove(rp2);
                        break;
                    }
                }
            }

            paths.Remove(nodes[coord]);
            nodes.Remove(coord);
        }

        private bool BuildPath(DDDCoordinate c1, DDDCoordinate c2, RoadPathType type)
        {
            RoadPath oneWay;
            RoadPath twoWay;

            RoadNode nodeC1 = nodes[c1];
            RoadNode nodeC2 = nodes[c2];

            List<Vector3> stepsOne;
            List<Vector3> stepsTwo;

            if (type == RoadPathType.Road)
            {
                stepsOne = GetPathSteps(c1, c2, type);
                stepsTwo = new List<Vector3>(stepsOne);
                stepsTwo.Reverse();
            }
            else
            {
                stepsOne = GetPathSteps(c1, c2, type);
                stepsTwo = GetPathSteps(c2, c1, type);
                
            }

            oneWay = new RoadPath(nodes[c1], type, nodes[c2], stepsOne);
            twoWay = new RoadPath(nodes[c2], type, nodes[c1], stepsTwo);

            if (paths.ContainsKey(nodeC1))
            {
                List<RoadPath> curr = paths[nodeC1];
                curr.Add(oneWay);
            }
            else
            {
                List<RoadPath> newList = new List<RoadPath>();
                newList.Add(oneWay);
                paths[nodes[c1]] = newList;
            }

            if (paths.ContainsKey(nodes[c2]))
            {
                List<RoadPath> curr = paths[nodeC2];
                curr.Add(twoWay);
            }
            else
            {
                List<RoadPath> newList = new List<RoadPath>();
                newList.Add(twoWay);
                paths[nodeC2] = newList;
            }

            return true;
        }

        private List<Vector3> GetPathSteps(DDDCoordinate c1, DDDCoordinate c2, RoadPathType roadType)
        {
            List<Vector3> list = new List<Vector3>();

            RotateType rotType = RotateType.Zero;
            if (c1.X < c2.X) rotType = RotateType.Ninety;
            if (c1.Z > c2.Z) rotType = RotateType.OneEighty;
            if (c1.X > c2.X) rotType = RotateType.TwoSeventy;

            Vector3 start = Vector3.Empty;
            start.X = c1.X + xChange[(int)rotType];
            start.Y = Game.gameWorld.Map.GetTileMaxHeight(c1.X, c1.Z);

            if (nodes[c1].NodeType == RoadPathType.Tunnel)
                start.Y = Game.gameWorld.Map.GetTileMinHeight(c1.X, c1.Z);

            start.Z = c1.Z + zChange[(int)rotType];

            Vector3 finish = Vector3.Empty;
            finish.X = c2.X + xChange[(((int)rotType) + 2) % 4];
            finish.Y = Game.gameWorld.Map.GetTileMaxHeight(c2.X, c2.Z);

            if (nodes[c2].NodeType == RoadPathType.Tunnel)
                finish.Y = Game.gameWorld.Map.GetTileMinHeight(c2.X, c2.Z);

            finish.Z = c2.Z + zChange[(((int)rotType) + 2) % 4];

            int incX = 1;
            int incZ = 0;
            int mult = 1;

            int startAt = c1.X;
            int getTo = c2.X;

            if (c1.X == c2.X)
            {
                incX = 0; incZ = 1;
                startAt = c1.Z; getTo = c2.Z;
            }

            if (startAt > getTo)
            {
                incX *= -1;
                incZ *= -1;
                mult = -1;
            }

            if (roadType == RoadPathType.Road)
            {

                list.Add(start);

                int currX = c1.X + incX;
                int currZ = c1.Z + incZ;

                Vector3 lastOne = start;

                Vector3 nextOne = new Vector3(c1.X + incX + xChange[(int)rotType],
                                                    Game.gameWorld.Map.GetTileHeight(c1.X + incX, c1.Z + incZ),
                                                    c1.Z + incZ + zChange[(int)rotType]);
                startAt += mult;

                while (startAt != getTo)
                {
                    if (lastOne.Y > nextOne.Y)
                    {
                        list.Add(new Vector3(lastOne.X, Game.gameWorld.Map.GetTileMinHeight(currX - incX, currZ - incZ), lastOne.Z));
                    }
                    else if (lastOne.Y < nextOne.Y)
                    {
                        list.Add(new Vector3(lastOne.X, Game.gameWorld.Map.GetTileMaxHeight(currX - incX, currZ - incZ), lastOne.Z));
                    }
                    else if (lastOne.Y == nextOne.Y)
                    {
                        if (Game.gameWorld.Map.GetTileSlopeType(currX - incX, currZ - incZ) == SlopeType.FlatSlope &&
                            Game.gameWorld.Map.GetTileSlopeType(currX, currZ) == SlopeType.FlatSlope)
                        {
                            list.Add(new Vector3(lastOne.X, Game.gameWorld.Map.GetTileMaxHeight(currX - incX, currZ - incZ), lastOne.Z));
                        }
                    }

                    lastOne = nextOne;
                    nextOne = new Vector3(nextOne.X + incX, Game.gameWorld.Map.GetTileHeight(currX + incX, currZ + incZ), nextOne.Z + incZ);
                    startAt += mult;

                    currX += incX;
                    currZ += incZ;


                }

                if (finish != start)
                    list.Add(finish);

            }
            else
            {
                start.Y = Game.gameWorld.Map.GetTileMinHeight(c1.X, c1.Z);
                finish.Y = Game.gameWorld.Map.GetTileMinHeight(c2.X, c2.Z);

                list.Add(start);
                list.Add(finish);
            }
            


            return list;
        }

        private bool CanConnect(DDDCoordinate coord, DDDCoordinate otherCoord)
        {
            RoadNode first = nodes[coord];
            RoadNode other = nodes[otherCoord];

            return first.CanConnectTo(other);
        }

        private List<RoadPath> GetPathsTo(DDDCoordinate neighbour)
        {
            List<RoadPath> pathsTo = new List<RoadPath>();

            foreach (List<RoadPath> rps in paths.Values)
            {
                foreach (RoadPath rp in rps)
                    if (rp.Destination.Coordinate.Equals(neighbour)) pathsTo.Add(rp);
            }

            return pathsTo;
        }

        private DDDCoordinate GetAdjacentTile(DDDCoordinate coord, RotateType rotType)
        {
            DDDCoordinate adjacentTile = new DDDCoordinate(coord.X, coord.Y, coord.Z);

            if (rotType == RotateType.Zero) { adjacentTile.Z++; }
            else if (rotType == RotateType.Ninety) { adjacentTile.X++; }
            else if (rotType == RotateType.OneEighty) { adjacentTile.Z--; }
            else { adjacentTile.X--; }

            if (nodes.ContainsKey(adjacentTile))
            {
                return adjacentTile;
            }

            adjacentTile.Y += 1;

            if (nodes.ContainsKey(adjacentTile))
            {
                return adjacentTile;
            }

            adjacentTile.Y += 1;

            if (nodes.ContainsKey(adjacentTile))
            {
                return adjacentTile;
            }

            adjacentTile.Y -= 3;

            if (nodes.ContainsKey(adjacentTile))
            {
                return adjacentTile;
            }

            adjacentTile.Y -= 1;

            if (nodes.ContainsKey(adjacentTile))
            {
                return adjacentTile;
            }

            return null;
        }

        

        private void RemovePathsContaining(DDDCoordinate coord)
        {
            List<RoadPath> pathsToRemove = new List<RoadPath>();

            foreach (List<RoadPath> rps in paths.Values)
            {
                foreach (RoadPath rp in rps)
                {
                    if (RoadPath.IsBetween(rp.Source.Coordinate, rp.Destination.Coordinate, coord))
                    {
                        pathsToRemove.Add(rp);
                    }
                }
            }

            foreach (RoadPath path in pathsToRemove)
            {
                paths[nodes[path.Source.Coordinate]].Remove(path);
            }

            List<RoadNode> toRemove = new List<RoadNode>();

            foreach (RoadNode key in paths.Keys)
                if (paths[key].Count == 0) toRemove.Add(key);

            foreach (RoadNode node in toRemove)
                paths.Remove(node);
        }

        private List<RoadPath> GetPathsContaining(DDDCoordinate coord)
        {
            //Could optimise by only looking in x and z directions of the coordinate

            List<RoadPath> pathsContaining = new List<RoadPath>();

            foreach (List<RoadPath> rps in paths.Values)
            {
                foreach (RoadPath rp in rps)
                {
                    if (RoadPath.IsBetween(rp.Source.Coordinate, rp.Destination.Coordinate, coord))
                    {
                        pathsContaining.Add(rp);
                    }
                }
            }

            return pathsContaining;
        }

        internal RoadPath AStarPathFind(DDDCoordinate from, DDDCoordinate to)
        {
            if (from.Equals(to)) return null;

            AStarNode startNode = new AStarNode(null, from, 0, from.GridDistanceTo(to));

            if (!nodes.ContainsKey(from)) return null;

            if (!nodes.ContainsKey(to)) return null;

            List<AStarNode> solution = new List<AStarNode>();

            SortedNodeList openList = new SortedNodeList();
            List<AStarNode> closedList = new List<AStarNode>();

            openList.AddNode(startNode);

            while (openList.Size() > 0)
            {
                AStarNode current = openList.Pop();

                if (current.IsGoal(to))
                {
                    while (current != null)
                    {
                        solution.Insert(0, current);
                        current = current.Parent;
                    }
                    break;
                }

                List<AStarNode> successors = GetDescendants(current, to);

                foreach (AStarNode node in successors)
                {
                    AStarNode openNode = null;
                    if (openList.Contains(node)) openNode = openList.Fetch(node);
                    if ((openNode != null) && (node.TotalCost > openNode.TotalCost)) continue;


                    AStarNode closedNode = null;
                    if (closedList.Contains(node)) closedNode = closedList[closedList.IndexOf(node)];
                    if ((closedNode != null) && (node.TotalCost > closedNode.TotalCost)) continue;

                    openList.RemoveNode(openNode);
                    closedList.Remove(closedNode);

                    openList.AddNode(node);

                }

                closedList.Add(current);

            }

            if (solution.Count > 0)
            {
                List<RoadPath> pathsFromHere = paths[nodes[from]];

                foreach (RoadPath path in pathsFromHere)
                {
                    if (path.Destination.Coordinate.Equals(solution[1].Coordinate))
                    {
                        return path;
                    }
                }

                return null;
            }
            else
            {
                return null;
            }
        }

        public List<AStarNode> GetDescendants(AStarNode source, DDDCoordinate target)
        {
            DDDCoordinate nodeCoord = source.Coordinate;
            List<RoadPath> descendantList = new List<RoadPath>();

            RoadNode node = null;

            if (nodes.ContainsKey(nodeCoord)) node = nodes[nodeCoord];

            if (node != null && paths.ContainsKey(node))
            {
                descendantList = paths[node];
            }

            List<AStarNode> descendants = new List<AStarNode>();

            foreach (RoadPath rp in descendantList)
            {
                int costToHere = source.CostToHere + rp.GetPathLength();
                int costToDestination = rp.Destination.Coordinate.GridDistanceTo(target);

                AStarNode temp = new AStarNode(source, rp.Destination.Coordinate, costToHere, costToDestination);
                descendants.Add(temp);
            }

            return descendants;
        }

        public TileType GetRoadType(DDDCoordinate coord)
        {
            if (nodes.ContainsKey(coord))
                return nodes[coord].RoadType;
            else
            {
                List<RoadPath> containing = GetPathsContaining(coord);

                if (containing.Count == 0)
                    return TileType.Grass;
                else
                    return TileType.RoadStraight;
            }
        }

        internal RotateType GetRotateType(DDDCoordinate coord)
        {
            if (nodes.ContainsKey(coord))
                return nodes[coord].RotateAngle;
            else
            {
                List<RoadPath> containing = GetPathsContaining(coord);

                if (containing.Count == 0)
                    return RotateType.Invalid;
                else
                {
                    if (containing[0].Source.Coordinate.X != containing[0].Destination.Coordinate.X)
                        return RotateType.Ninety;
                    return RotateType.Zero;
                }
            }
        }
    }

    public struct RoadStrip
    {
        public List<DDDCoordinate> coords;
        public RotateType start;

        public RoadStrip(List<DDDCoordinate> coords, RotateType start)
        {
            this.coords = coords;
            this.start = start;
        }
    }
}
